package com.test.sort;

import java.util.Arrays;

/**
 * @author: 蒿雨
 * @create: 2022-02-18 18:46
 * @description:基数排序法（桶排序）二次测试
 */
public class RadixSortAgain {
    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214};
        radisSrot(arr);
        System.out.println(Arrays.toString(arr));

    }

    //基数排序法
    private static void radisSrot(int[] arr) {

        //1、得到数组中最大的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        System.out.printf("求出最大的位数%d\n", max);

        Integer maxLength = (max + "").length();
        System.out.printf("最大的位数%d", maxLength);

        //2、创建桶
        // 【10】：个位只能是从0到910个数
        //【6】：最大每个桶只可能放下数组的最大个数
        int[][] bucket = new int[10][arr.length];

        //3、创建计算桶的最大个数（用来把桶中的元素复位）
        // 【10】：个位只能是从0到910个数
        int[] bucketElementCounts = new int[10];

        //4、循环三轮
        //i:用来循环最大位数的轮数
        //n:用来控制每次操作的位数成10倍增长
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {

            //循环这六个数
            for (int j = 0; j < arr.length; j++) {
                //①取出个位数并放入桶
                int digiOfElement = arr[j] / n % 10;
                //放入桶中
                //bucket[3][0]=53;
                bucket[digiOfElement][bucketElementCounts[digiOfElement]] = arr[j];
                //此处++是为了如果有下个数加进来的位置
                bucketElementCounts[digiOfElement]++;
            }
            //5、要通过元素数组把桶中元素依次复位
            //index:用来控制数组的复位
            int index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {

                if (bucketElementCounts[k] != 0) {
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //从桶中取出元素并排序
                        arr[index++] = bucket[k][l];
                    }

                }

                //每次循环清空元素桶
                bucketElementCounts[k] = 0;
            }

        }


    }
}
